use crate::error::Result;
use crate::storage::data_types::traits::{DataType, ListOperations};
use std::any::Any;
use std::collections::VecDeque;

/// List data type implementation
/// 
/// Represents a Redis list value, which is an ordered collection of strings.
/// Implemented using VecDeque for efficient operations at both ends.
#[derive(Debug, Clone)]
pub struct ListType {
    data: VecDeque<String>,
}

impl ListType {
    /// Create a new empty list
    pub fn new() -> Self {
        Self {
            data: VecDeque::new(),
        }
    }
    
    /// Create a list from an existing VecDeque
    pub fn from_deque(data: VecDeque<String>) -> Self {
        Self { data }
    }
    
    /// Create a list from a Vec
    pub fn from_vec(data: Vec<String>) -> Self {
        Self {
            data: VecDeque::from(data),
        }
    }
    
    /// Get the underlying VecDeque reference
    pub fn as_deque(&self) -> &VecDeque<String> {
        &self.data
    }
    
    /// Get the underlying VecDeque mutable reference
    pub fn as_deque_mut(&mut self) -> &mut VecDeque<String> {
        &mut self.data
    }
    
    /// Clear all elements
    pub fn clear(&mut self) {
        self.data.clear();
    }
    
    /// Convert to Vec
    pub fn to_vec(&self) -> Vec<String> {
        self.data.iter().cloned().collect()
    }
    
    /// Helper to convert negative indices to positive indices
    fn normalize_index(&self, index: i64) -> Option<usize> {
        let len = self.data.len() as i64;
        
        if index >= 0 {
            if index < len {
                Some(index as usize)
            } else {
                None
            }
        } else {
            let positive_index = len + index;
            if positive_index >= 0 {
                Some(positive_index as usize)
            } else {
                None
            }
        }
    }
    
    /// Helper to normalize range indices for LRANGE and LTRIM
    fn normalize_range(&self, start: i64, stop: i64) -> (usize, usize) {
        let len = self.data.len() as i64;
        
        // Normalize start
        let start = if start < 0 {
            std::cmp::max(0, len + start)
        } else {
            std::cmp::min(start, len)
        } as usize;
        
        // Normalize stop
        let stop = if stop < 0 {
            std::cmp::max(-1, len + stop)
        } else {
            std::cmp::min(stop, len - 1)
        } as usize;
        
        (start, stop)
    }
    
    /// Calculate memory usage
    fn calculate_memory_usage(&self) -> usize {
        let base_size = std::mem::size_of::<Self>();
        let deque_overhead = self.data.capacity() * std::mem::size_of::<String>();
        let content_size: usize = self.data
            .iter()
            .map(|s| s.len())
            .sum();
        
        base_size + deque_overhead + content_size
    }
}

impl Default for ListType {
    fn default() -> Self {
        Self::new()
    }
}

impl DataType for ListType {
    fn type_name(&self) -> &'static str {
        "list"
    }
    
    fn debug_string(&self) -> String {
        format!("ListType({} elements)", self.data.len())
    }
    
    fn clone_data(&self) -> Box<dyn DataType> {
        Box::new(self.clone())
    }
    
    fn is_empty(&self) -> bool {
        self.data.is_empty()
    }
    
    fn memory_usage(&self) -> usize {
        self.calculate_memory_usage()
    }
    
    fn as_any(&self) -> &dyn Any {
        self
    }
    
    fn as_any_mut(&mut self) -> &mut dyn Any {
        self
    }
}

impl ListOperations for ListType {
    fn lpush(&mut self, values: Vec<String>) -> Result<usize> {
        // Push values to the left (front) in reverse order to maintain Redis semantics
        for value in values.into_iter().rev() {
            self.data.push_front(value);
        }
        Ok(self.data.len())
    }
    
    fn rpush(&mut self, values: Vec<String>) -> Result<usize> {
        // Push values to the right (back)
        for value in values {
            self.data.push_back(value);
        }
        Ok(self.data.len())
    }
    
    fn lpop(&mut self) -> Result<Option<String>> {
        Ok(self.data.pop_front())
    }
    
    fn rpop(&mut self) -> Result<Option<String>> {
        Ok(self.data.pop_back())
    }
    
    fn llen(&self) -> Result<usize> {
        Ok(self.data.len())
    }
    
    fn lindex(&self, index: i64) -> Result<Option<String>> {
        match self.normalize_index(index) {
            Some(idx) => Ok(self.data.get(idx).cloned()),
            None => Ok(None),
        }
    }
    
    fn lset(&mut self, index: i64, value: String) -> Result<()> {
        match self.normalize_index(index) {
            Some(idx) => {
                if let Some(element) = self.data.get_mut(idx) {
                    *element = value;
                    Ok(())
                } else {
                    Err(crate::error::StorageError::IndexOutOfBounds { index })
                }
            }
            None => Err(crate::error::StorageError::IndexOutOfBounds { index }),
        }
    }
    
    fn lrange(&self, start: i64, stop: i64) -> Result<Vec<String>> {
        if self.data.is_empty() {
            return Ok(Vec::new());
        }
        
        let (start_idx, stop_idx) = self.normalize_range(start, stop);
        
        if start_idx > stop_idx || start_idx >= self.data.len() {
            return Ok(Vec::new());
        }
        
        let end_idx = std::cmp::min(stop_idx + 1, self.data.len());
        Ok(self.data
            .range(start_idx..end_idx)
            .cloned()
            .collect())
    }
    
    fn ltrim(&mut self, start: i64, stop: i64) -> Result<()> {
        if self.data.is_empty() {
            return Ok(());
        }
        
        let (start_idx, stop_idx) = self.normalize_range(start, stop);
        
        if start_idx > stop_idx || start_idx >= self.data.len() {
            self.data.clear();
            return Ok(());
        }
        
        let end_idx = std::cmp::min(stop_idx + 1, self.data.len());
        
        // Keep only elements in the range [start_idx, end_idx)
        let mut new_data = VecDeque::new();
        for (i, item) in self.data.iter().enumerate() {
            if i >= start_idx && i < end_idx {
                new_data.push_back(item.clone());
            }
        }
        self.data = new_data;
        
        Ok(())
    }
    
    fn lrem(&mut self, count: i64, value: &str) -> Result<usize> {
        let mut removed_count = 0;
        
        if count == 0 {
            // Remove all occurrences
            self.data.retain(|item| {
                if item == value {
                    removed_count += 1;
                    false
                } else {
                    true
                }
            });
        } else if count > 0 {
            // Remove first count occurrences
            let mut remaining = count as usize;
            let mut i = 0;
            while i < self.data.len() && remaining > 0 {
                if self.data[i] == value {
                    self.data.remove(i);
                    removed_count += 1;
                    remaining -= 1;
                } else {
                    i += 1;
                }
            }
        } else {
            // Remove last count occurrences (count is negative)
            let mut remaining = (-count) as usize;
            let mut i = self.data.len();
            while i > 0 && remaining > 0 {
                i -= 1;
                if self.data[i] == value {
                    self.data.remove(i);
                    removed_count += 1;
                    remaining -= 1;
                }
            }
        }
        
        Ok(removed_count)
    }
    
    fn linsert(&mut self, before: bool, pivot: &str, value: String) -> Result<i64> {
        // Find the pivot element
        for (i, item) in self.data.iter().enumerate() {
            if item == pivot {
                if before {
                    self.data.insert(i, value);
                } else {
                    self.data.insert(i + 1, value);
                }
                return Ok(self.data.len() as i64);
            }
        }
        
        // Pivot not found
        Ok(-1)
    }
}

impl From<Vec<String>> for ListType {
    fn from(data: Vec<String>) -> Self {
        Self::from_vec(data)
    }
}

impl From<VecDeque<String>> for ListType {
    fn from(data: VecDeque<String>) -> Self {
        Self::from_deque(data)
    }
}

impl From<&[String]> for ListType {
    fn from(data: &[String]) -> Self {
        Self::from_vec(data.to_vec())
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    
    #[test]
    fn test_list_basic_operations() {
        let mut list = ListType::new();
        
        assert!(list.is_empty());
        assert_eq!(list.llen().unwrap(), 0);
        
        // Test rpush
        let len = list.rpush(vec!["a".to_string(), "b".to_string()]).unwrap();
        assert_eq!(len, 2);
        assert_eq!(list.llen().unwrap(), 2);
        
        // Test lpush
        let len = list.lpush(vec!["c".to_string(), "d".to_string()]).unwrap();
        assert_eq!(len, 4);
        // After lpush with ["c", "d"], order should be: ["d", "c", "a", "b"]
    }
    
    #[test]
    fn test_list_push_pop() {
        let mut list = ListType::new();
        
        // Push elements
        list.rpush(vec!["1".to_string(), "2".to_string(), "3".to_string()]).unwrap();
        
        // Test rpop
        assert_eq!(list.rpop().unwrap(), Some("3".to_string()));
        assert_eq!(list.llen().unwrap(), 2);
        
        // Test lpop
        assert_eq!(list.lpop().unwrap(), Some("1".to_string()));
        assert_eq!(list.llen().unwrap(), 1);
        
        // Test pop from empty list
        list.lpop().unwrap(); // Remove last element
        assert_eq!(list.lpop().unwrap(), None);
        assert_eq!(list.rpop().unwrap(), None);
    }
    
    #[test]
    fn test_list_index_operations() {
        let mut list = ListType::new();
        list.rpush(vec!["a".to_string(), "b".to_string(), "c".to_string()]).unwrap();
        
        // Test lindex
        assert_eq!(list.lindex(0).unwrap(), Some("a".to_string()));
        assert_eq!(list.lindex(1).unwrap(), Some("b".to_string()));
        assert_eq!(list.lindex(2).unwrap(), Some("c".to_string()));
        assert_eq!(list.lindex(3).unwrap(), None);
        
        // Test negative indices
        assert_eq!(list.lindex(-1).unwrap(), Some("c".to_string()));
        assert_eq!(list.lindex(-2).unwrap(), Some("b".to_string()));
        assert_eq!(list.lindex(-3).unwrap(), Some("a".to_string()));
        assert_eq!(list.lindex(-4).unwrap(), None);
        
        // Test lset
        list.lset(1, "modified".to_string()).unwrap();
        assert_eq!(list.lindex(1).unwrap(), Some("modified".to_string()));
        
        // Test lset with invalid index
        assert!(list.lset(10, "invalid".to_string()).is_err());
    }
    
    #[test]
    fn test_list_range_operations() {
        let mut list = ListType::new();
        list.rpush(vec!["a".to_string(), "b".to_string(), "c".to_string(), "d".to_string(), "e".to_string()]).unwrap();
        
        // Test lrange
        assert_eq!(list.lrange(0, 2).unwrap(), vec!["a", "b", "c"]);
        assert_eq!(list.lrange(1, 3).unwrap(), vec!["b", "c", "d"]);
        assert_eq!(list.lrange(0, -1).unwrap(), vec!["a", "b", "c", "d", "e"]);
        assert_eq!(list.lrange(-3, -1).unwrap(), vec!["c", "d", "e"]);
        assert_eq!(list.lrange(10, 20).unwrap(), Vec::<String>::new());
        
        // Test ltrim
        list.ltrim(1, 3).unwrap();
        assert_eq!(list.llen().unwrap(), 3);
        assert_eq!(list.lrange(0, -1).unwrap(), vec!["b", "c", "d"]);
    }
    
    #[test]
    fn test_list_remove_operations() {
        let mut list = ListType::new();
        list.rpush(vec!["a".to_string(), "b".to_string(), "a".to_string(), "c".to_string(), "a".to_string()]).unwrap();
        
        // Remove first 2 occurrences of "a"
        let removed = list.lrem(2, "a").unwrap();
        assert_eq!(removed, 2);
        assert_eq!(list.lrange(0, -1).unwrap(), vec!["b", "c", "a"]);
        
        // Remove last 1 occurrence of "a"
        let removed = list.lrem(-1, "a").unwrap();
        assert_eq!(removed, 1);
        assert_eq!(list.lrange(0, -1).unwrap(), vec!["b", "c"]);
        
        // Remove all occurrences
        list.rpush(vec!["x".to_string(), "x".to_string()]).unwrap();
        let removed = list.lrem(0, "x").unwrap();
        assert_eq!(removed, 2);
        assert_eq!(list.lrange(0, -1).unwrap(), vec!["b", "c"]);
    }
    
    #[test]
    fn test_list_insert_operations() {
        let mut list = ListType::new();
        list.rpush(vec!["a".to_string(), "b".to_string(), "c".to_string()]).unwrap();
        
        // Insert before "b"
        let len = list.linsert(true, "b", "x".to_string()).unwrap();
        assert_eq!(len, 4);
        assert_eq!(list.lrange(0, -1).unwrap(), vec!["a", "x", "b", "c"]);
        
        // Insert after "b"
        let len = list.linsert(false, "b", "y".to_string()).unwrap();
        assert_eq!(len, 5);
        assert_eq!(list.lrange(0, -1).unwrap(), vec!["a", "x", "b", "y", "c"]);
        
        // Insert with non-existent pivot
        let len = list.linsert(true, "z", "w".to_string()).unwrap();
        assert_eq!(len, -1);
        assert_eq!(list.llen().unwrap(), 5); // No change
    }
    
    #[test]
    fn test_list_conversions() {
        let vec_data = vec!["a".to_string(), "b".to_string(), "c".to_string()];
        let list = ListType::from(vec_data.clone());
        
        assert_eq!(list.llen().unwrap(), 3);
        assert_eq!(list.to_vec(), vec_data);
        
        let deque_data = VecDeque::from(vec!["x".to_string(), "y".to_string()]);
        let list = ListType::from(deque_data);
        assert_eq!(list.llen().unwrap(), 2);
    }
    
    #[test]
    fn test_data_type_trait() {
        let list = ListType::new();
        
        assert_eq!(list.type_name(), "list");
        assert!(list.is_empty());
        assert!(list.memory_usage() > 0);
        
        let cloned = list.clone_data();
        assert_eq!(cloned.type_name(), "list");
    }
}